package DynamicProgramming.Medium;

import java.util.List;

public class LC0139 {
    public boolean wordBreak(String s, List<String> wordDict) {
        int[] dp = new int[s.length() + 1]; // dp[i]取各个值的含义：0 - 未计算；1 - 可以拼接；-1 - 不可拼接。
        dp[0] = 1;
        for (int i = 1; i <= s.length(); i++) { // i: 子串长度
            for (String word : wordDict) {
                if (word.length() > i) continue;

                if (s.substring(i - word.length(), i).equals(word) && dp[i - word.length()] > 0) {
                    dp[i] = 1;
                    break;
                }

            }
            if (dp[i] == 0) dp[i] = -1;
        }

        return dp[s.length()] == 1;
    }
}
